The rate of digital transmission is getting faster. Errors arising in the transmission channel, due to disturbances such as noise, fading, interferences, and so forth, make the transmission unreliable. Therefore, several techniques are used for the automatic correction of such errors on reception.
This is usually achieved by protecting the information to be sent by means of error correction codes. Considering such information as being divided in words of k bits each, the block code (n,k) follows a relationship law coupling each word of information to a n bit long code with n&gt;k. The n-k difference is called redundancy.
Cyclic codes are class of such kind of codes, where all the words in the code can be obtained starting from a word in the code means by a processes of cyclic shifting.
It is helpful to use polynomials to represent both the information and the code words. So, the information word, a k-tuple (i.sub.o, i.sub.i, . . . i.sub.k-1), will be represented by the polynomial i.sub.0 +i.sub.1 x+ . . . +i.sub.k-1 x.sup.k-1 =i(x), and the code word, an n-tuple (c.sub.o, c.sub.1. . . c.sub.n-1), will be represented by c.sub.0 +c.sub.1 x+ . . . +c.sub.n-1 x.sup.n-1 =c(x). The law of coding itself can be represented by a g(x) polynomial of degree (n-k), the so-called generator, such that the code polynomial c(x) is obtained multiplying the g(x) polynomial by the polynomial i(x). An important class of such codes, able to contrast error bursts that are typical in memory channels (like radio channels affected by fading) is the class of the so-called Fire codes with GF(2), the above notation representing double value (0 and 1) Galois fields. The generator polynomial of such kind of codes can be expressed in a general form by: EQU g(x)=(x.sup.2t-1 -1)p(x) (1)
where p(x) is a m degree irreducible polynomial.
Let ro be the period of p(x), i.e. the smallest integer such that p(x) divides (x.sup.ro +1) and t a positive integer, smaller or equal to m, such that (2t-1) is not divisible by ro.
The code length (the number of bits in each code word) is the least common multiple of (2t-1) and ro, and the number of redundant bits is (m+2t-1).
Below, the Fire codes are represented by the notation F(n,k), where n indicates the length of the coded word, k is the length of the information word and (n-k) is the redundancy.
A code with generator polynomial g(x) given by (1), for which the above conditions expressed or m, ro and (2t-1) are verified, is able to correct any single error burst (i.e. the sequence of bits included between the first and the last erroneous bit in the code word) shorter or equal to t, and also to detect the presence of error bursts longer than t.
Fire codes can be decoded using decoders belong to the family of "Error Trapping" decoders. In such devices, the time required for correcting the errors is equal to n cycles, n being the length of the code word.
In technical literature, there are some known decoders studied "ad hoc" for the Fire codes, able to correct errors in a shorter time. Once of such devices is discussed in IBM Technical Disclosure Bulletin, Vol. 30 No. 5 October 1987. This article describes a traditional Fire-Code Decoding technique in which the received code word is considered as a single polynomial from which a single syndrome is computed by shifting in one direction and an error correction is accomplished by shifting in the reverse direction. Another of such devices has been proposed by R. T. Chien in his paper "Burst-correcting codes with high-speed decoding", IEEE Trans. on Information Theory, Vol. IT-15, Nr. 1, January 1969, pages 109 to 113.
This document discloses a process for the decoding of a shortened cyclic binary code, able to correct single error bursts b(x) of given length t or shorter, specifically a F(n-b, k-b) shortened Fire code, with generator polynomial g(x)=(x.sup.2t-1 +1).p(x), p(x) being a prime polynomial over GF(2) with period ro, satisfying the ro&gt;(n-b), condition, where:
the received code word r(x) is buffered in a shift register as a received vector and the syndrome polynomials s1(x) and s2(x) are calculated in (n-b) cycles; PA1 the polynomial s1(x) is cyclic shifted a .GAMMA.1 number of times in a first direction until all zeros are obtained in the (t-1) higher order positions, so to trap the burst b(x) of length t in the lowest order positions. PA1 p(x) primitive on GF(2); PA1 ro and (2t-1) prime to each other; PA1 N=n-b&lt;ro, and preferably &lt;ro/2. PA1 a) As the word in the shortened code is of length N, the constraint n-q&lt;N applies to the generic component of the polynomial representing the received code word and to the burst x.sup.n-q b(x) to be corrected. PA1 b) For n-q=ro-1, .GAMMA.2=1, for n-q=ro-2 it is .GAMMA.2=2, . . . for n=q=ro-k it is .GAMMA.2=k. PA1 c) Being N.ltoreq.ro, let be D=ro-N, the constraint on (n-q) in item a) becomes n-q.ltoreq.ro-D-1. PA1 d) The constraint on n-q in item c), because of the remarks performed in item b), causes a constraint for .GAMMA.2. PA1 e) the shift Register "Error Locator" is a sequential machine, reaching the state at which is .GAMMA.2=D+1 only after the state transitions with .GAMMA.2=1, .GAMMA.2=2, . . . .GAMMA.2=D+1. So, the burst x.sup.N-1 b(x), being (n-q=N-1), is corrected after D+1 cycles, and the burst x.sup.N-.tau. b(x), being (n-q=N-.tau.), is corrected after D+.tau. cycles. Therefore, even if there is a considerable shortening of the code length, Chien's decoder still takes at least (ro-N+1) stages to correct the errors, making it useless to handle a shortened code. Coming back to the above mentioned example concerning ETSI/GSM, even if the code has a length n=224, the error correction process would consist of at least (ro-N+1)=130848 cycles. PA1 the received r(x) code word is stored and the s1(x) and s2(x) syndrome polynomials are calculated in (n-b) cycles; PA1 the s1(x) polynomial is cyclically shifted a .GAMMA.1 number of times in a first direction until all zeros are obtained in the t-1) positions of the higher order so to trap the burst b(x) of length t in the lower order positions; PA1 this procedure is characterized by: PA1 shifting of the remainder polynomial s2(x), in an opposite direction to the above mentioned first one, until the pattern of the t bits of the lowest order becomes the same as that of the already mentioned burst b(x) of length t, and to calculate a .GAMMA.2 number equal to (ro-h), where h is the amount of shift operations performed; PA1 calculate (n-q) by the relation: EQU q=.GAMMA.1.A2.ro+.GAMMA.2.A1.(2t-1) mod(n) PA1 perform the correction adding modulo 2 the polynomial (x.sup.n-q).b(x) to the received vector. PA1 input means for a code word (r(X)); PA1 a first unidirectional shift register, with (2t-1) stages, serially connected to said input means; PA1 a second unidirectional shift register, with m stages, serially connected to said input means; PA1 a test for zero circuit parallely connected to the (t-1) highest order states of said first register; PA1 first modulo (2t-1) counting means, able to compute the number of shifting operations performed by said first register; characterized by further comprising: PA1 a third unidirectional shift register with m stages, parallely connected with said second register and capable of shifting data in a direction opposed to that of the above first and second registers; PA1 a comparing device, parallely connected between the t lowest order stages of said first unidirectional shift register and said third shift register, the output of said comparing device being connected to second modulo ro counting means able to compute the number of shifting operations performed by said second register; PA1 a computing circuit connected to the outputs of said first and second counting means for computing an (n-q) number able to allow, in the case, the correction of the error burst in said code word (r(X)). PA1 input means for a code word (r(X)); PA1 a first unidirectional shift register with (2t-1) stages, serially connected to said input means; PA1 a second shift register, with m stages, serially connected to said input means; PA1 a test for zero circuit parallely connected to the (t-1)) highest order stages of said first register; PA1 first modulo (2t-1) counting means, able to compute the number of shifting operations performed by said first register; characterized in that PA1 said second shift register is a bidirectional shift register, and in that said device further comprises: PA1 a comparing device parallely connected between the t lowest order stages of said first unidirectional shift register and said second bidirectional shift register, the output of said comparing device being connected to second modulo ro counting means able to compute the number of shifting operations performed by said second register; PA1 a computing circuit connected to the outputs of said first and second counting means for computing an (n-q) number able to allow, in the case, the correction of the error burst in said code word (r(X)).
Once the code word has been inputted, Chien's decoder can correct errors in a number of cycles (this being the delay with which the correct code can be obtained) given at most by: EQU (2t-2)+(ro-1) (2)
As for a Fire code, n is the least common multiple of (2t-1) and ro, and as (2t-1) is not divisible by ro, n can at most be equal to ro.(2t-1).
A normal "Error Trapping" decoder would at most take ro.(2t-1) cycles to correct errors. Such value is much larger than the one given by expression (2), and this justifies the given definition for Chien's device as a high speed one.
The basic idea in Chien's decoder is that of using as syndrome a couple of polynomials, s1(x) and s2(x) , where s1(x) is the remainder polynomial obtained by dividing the received polynomial r(x) by the factor (x.sup.2t-1 +1) in the generator polynomial, and s2(x) is the remainder polynomial obtained by dividing the received polynomial r(x) by the factor p(x) in the generator polynomial r(x) by the factor p(x) in the generator polynomial. Above we have used r(x) to represented the received code word that, eventually contains errors.
Chien's decoder basically consists of two loop back shift registers. Both are fed by the bit sequence received in each generic code word. The first register, called "Error Pattern Register", consists of (2t-1) stages and is used to compute the polynomial s1(x), The second Register, called "Error Location Register", consists of (2t-1) stages and is used to compute the polynomial s1(x). The second Register, called "Error Location Register" consists of m stages, and is used to calculate the polynomial s2(x).
If both the polynomials s1(x) and s2(x) are null polynomials, no correction is applied, and the device only performs the decoding of the received code word which is error free.
If just one of the two polynomials s1(x) and s2(x) is not a null polynomial, then the device does not decode but detects the presence of errors (the error burst being greater than t).
Finally, if both polynomials s1(x) and s2(x) are not null polynomials, then the error correction process is started, at the end of which the decoding is performed (for error bursts of length&lt;=t).
The correction algorithm is accomplished in four phases: